package com.leetcode.algorithm.y22.m09.w2;

import com.leetcode.algorithm.common.ListNode;

/**
 * 148. 排序链表
 * 
 * https://leetcode.cn/problems/sort-list/
 * 
 * @author jie.deng
 *
 */
class Question0148Solution01 {

	public ListNode sortList(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		ListNode tail = divide(head);
		head = sortList(head);
		tail = sortList(tail);
		head = merge(head, tail);
		return head;
	}

	private ListNode merge(ListNode l1, ListNode l2) {
		if (l1 == null) {
			return l2;
		} else if (l2 == null) {
			return l1;
		}
		ListNode l3 = new ListNode();
		ListNode cur = l3;
		while (l1 != null || l2 != null) {
			if (l1 == null) {
				cur.next = l2;
				break;
			} else if (l2 == null) {
				cur.next = l1;
				break;
			} else {
				if (l1.val < l2.val) {
					cur.next = l1;
					cur = cur.next;
					l1 = l1.next;
				} else {
					cur.next = l2;
					cur = cur.next;
					l2 = l2.next;
				}
			}
		}
		return l3.next;
	}

	private ListNode divide(ListNode head) {
		ListNode fast = head;
		ListNode slow = head;
		ListNode prev = null;
		while (fast != null && fast.next != null) {
			fast = fast.next.next;
			prev = slow;
			slow = slow.next;
		}
		prev.next = null;
		return slow;
	}

}